package dynamic;

/**题目：抢劫环形房子
 * y: a[]{8,1,2,9,6}
 * @Author Gavin
 * @date 2022.01.09 10:36
 */
public class solution_5 {
    /**
     * 解题思路：本题是一个动态规划题目，和solution_4解题思路是一样的
     * 只是本地是一个环形的房子，就是首尾是相邻的两个房子，所以不能同时抢
     * 首尾两个房子，所以思路就是去掉首或者尾按照连排的方式计算，然后比较求
     * 最大值就行
     */
    //Time:O(n) Space:O(1)
    public int solution(int[] nums){
        if(nums==null||nums.length==0)return 0;
        if(nums.length==1)return nums[0];
        int n=nums.length;
        return Math.max(help(nums,0,n-2),help(nums,1,n-1));
    }


    public int help(int[] nums,int start,int end){
       int prev1=0,prev2=0;
       for (int i=start;i<=end;++i){
           int cur=Math.max(prev1,prev2+nums[i]);
           prev2=prev1;
           prev1=cur;
       }
       return prev1;
    }
}
